\documentclass{ctexart}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{float}

\title{3.6.1 Theoretical questions}
\author{Shao kexin \\ student number: 3200103310}

\begin{document}
\maketitle
\section{$\uppercase\expandafter{\romannumeral1}$}
Solution:\\
From the question stem, we know that
\begin{displaymath}
\left\{ \begin{array}{l}
     p(1) = 1 \\
     p'(1) = -3 \\
     p''(1) = 6 \\
     p(0) = 0
\end{array} \right.
\end{displaymath}
So $p = 7*x^3 - 18*x^2 + 12*x$.\\
$s''(2) = p''(2) = -36 \neq 0$.\\
Thus, $s(x)$ is't a natural cubic spline.
\section{$\uppercase\expandafter{\romannumeral2}$}
$f_i = f(x_i), a = x_1 < x_2 < ... < x_n = b, s \in \mathbb{S}^1_2$
\subsection{(a)}
Solution:\\
In order to determine n quadratic polynomials, we need (n - 1)*(2 + 1) = 3*n - 3 conditions;\\
We already know n(since $f_i = s(x_i)$) + (n-2)*(2)(since $s_i^{(d)}(x_{i+1}) = s_{i+1}^{(d)}(x_{i+1}), d \in \{0, 1\}$) = 3*n - 4 conditions.\\
Hence, we still need one condition.
\subsection{(b)}
Solution:\\
$m_i = s'(x_i), p_i = s|_{[x_i, x_{i+1}]}, i = 1,2, ..., n-1$.\\
\begin{align}
  p_i &= f_i + m_i*(x-x_i) + \dfrac{\dfrac{f_{i+1}-f_i}{x_{i+1}-x_i}-m_i}{x_{i+1}-x_i}*(x-x_i)*(x-x_i) \notag \\
      &= f_i + m_i*(x-x_i) + \dfrac{(f_{i+1}-f_i)-m_i*(x_{i+1}-x_i)}{(x_{i+1}-x_i)^2}*(x-x_i)^2 \notag
\end{align}
\subsection{(c)}
Solution:\\
$p_i' = m_i + 2*\dfrac{(f_{i+1}-f_i)-m_i*(x_{i+1}-x_i)}{(x_{i+1}-x_i)^2}*(x-x_i)$\\
$p_i'(x_{i+1}) = p_{i+1}'(x_{i+1})$\\
$2*\dfrac{f_{i+1}-f_i}{x_{i+1}-x_i} - m_i = m_{i+1}$\\
Therefore we can get $m_i, \forall i = 1, 2, 3, ...$ if we know $m_0$.
\section{$\uppercase\expandafter{\romannumeral3}$}
Solution:\\
Since $s_1(x) = 1 + c*(x + 1)^3$, we can get
\begin{displaymath}
\left\{ \begin{array}{l}
     s_1(x) = 1+c*(x+1)^3, x \in [-1, 0] \\
     s_1'(x) = 3*c*(x+1)^2, x \in [-1, 0] \\
     s_1''(x) = 6*c*(x+1), x \in [-1, 0] 
\end{array} \right.
\end{displaymath}
So we have $s_2(0) = s_1(0) = 1+c, s_2'(0) = s_1'(0) = 3*c, s_2''(0) = s_1''(0) = 6*c, s_2''(1) = 0$.\\
Thus $s_2(x) = 1+c + 3*c*x + 3*c*x^2 - c*x^3$.\\
As we know $s_2(1) = -1$, then $s_2(1) = 6*c + 1 = -1$ i.e. $c = -\frac{1}{3}$.
\section{$\uppercase\expandafter{\romannumeral4}$}
$f(x) = cos(\dfrac{\pi}{2}*x), x \in [-1,1]$
\subsection{(a)}
Solution:\\
\begin{displaymath}
  s(x) = \left\{ \begin{array}{ll}
    s_1(x) & , x \in [-1, 0]\\
    s_2(x) & , x \in [0, 1]
\end{array} \right.
\end{displaymath}
We know that
\begin{displaymath}
\left\{ \begin{array}{l}
     f(x) = cos(\dfrac{\pi}{2}*x) \\
     f'(x) = -\frac{\pi}{2}*sin(\frac{\pi}{2}*x) \\
     f''(x) = -\frac{\pi^2}{4}*cos(\frac{\pi}{2}*2)
\end{array} \right.
\end{displaymath}
Since s(x) is a natural cubic spline, $M_1 = s''(-1) = 0, M_3 = s''(1) = 0$\\
From Lemma 3.4 $\mu_2*M_1 + 2*M_2 + \lambda_2*M_3 = 6*f[x_1, x_2, x_3]$.\\
Then $f_1 = f(-1) = 0, f_2 = f(0) = 1, f_3 = f(1) = 0 \Rightarrow f[x_1, x_2, x_3] = -1 \Rightarrow M_2 = -3$.\\
In conclution, we can get the natural cubic spline interpolation to f on knots -1, 0, 1 
\begin{displaymath}
  s(x) = \left\{ \begin{array}{ll}
    s_1(x) = -\frac{1}{2}*x^3 - \frac{3}{2}*x^2 + 1 &, x \in [-1, 0] \\
    s_2(x) = \frac{1}{2}*x^3 - \frac{3}{2}*x^2 + 1 &, x \in [0, 1]
  \end{array} \right.
\end{displaymath}

\subsection{(b)}
Solution:\\
($\romannumeral1$)\\
$g(-1) = 0, g(0) = 1, g(1) = 0 \Rightarrow g(x) = -x^2 + 1$\\
$\int^1_{-1}[s''(x)]^2dx = \int^0_{-1}9*(x+1)dx + \int^1_{0}9*(x-1)dx = 6$\\
$\int^1_{-1}[g''(x)]^2dx = 8 > \int^1_{-1}[s''(x)]^2dx = 6$\\
($\romannumeral2$)\\
$\int^1_{-1}[f''(x)]^2dx = \frac{\pi^4}{16} > \int^1_{-1}[s''(x)]^2dx = 6$

\section{$\uppercase\expandafter{\romannumeral5}$}
\subsection{(a)}
Solution:\\
\begin{displaymath}
    B_i^0(x)=\left\{
        \begin{array}{l}
        1, \qquad \qquad  x \in (t_{i-1},t_i]\\
        0,  \qquad otherwise
        \end{array} 
    \right.
\end{displaymath}
Since
$$B_i^{n+1}(x) = \frac{x - t_{i-1}}{t_{i+n} - t_{i-1}}*B_i^n(x) + \frac{t_{i+n+1} - x}{t_{i+n+1} - t_i}*B_{i+1}^n(x),$$
we can get
\begin{displaymath}
    B_i^2(x)=\left\{
        \begin{array}{l}
        \frac{{(x-t_{i-1})}^2}{(t_{i+1}-t_{i-1})(t_i-t_{i-1})}, \qquad \qquad  x \in (t_{i-1},t_i]\\
        \frac{(x-t_{i-1})(t_{i+1}-x)}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{(t_{i+2}-x)(x-t_i)}{(t_{i+2}-t_{i})(t_{i+1}-t_i)}, \quad x \in (t_{i},t_{i+1}]\\
        \frac{{(t_{i+2}-x)}^2}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})},\qquad x \in (t_{i+1},t_{i+2}]\\
        0,  \qquad otherwise
        \end{array} 
    \right.
\end{displaymath}

\subsection{(b)}
Solution:\\
From (a), we can get
\begin{displaymath}
    \frac{\mathrm{d}}{\mathrm{d}x}B_i^2(x)=\left\{
        \begin{array}{l}
        \frac{2(x-t_{i-1})}{(t_{i+1}-t_{i-1})(t_i-t_{i-1})} , \qquad x \in (t_{i-1},t_i]\\
        \frac{-2x+t_{i+1}+t_{i-1}}{(t_{i+1}-t_{i-1})(t_{i+1}-t_i)}+\frac{-2x+t_i+t_{i+2}}{(t_{i+2}-t_i)(t_{i+1}-t_i)}, \qquad x \in (t_i,t_{i+1}]\\
        \frac{-2(t_{i+2}-x)}{(t_{i+2}-t_i)(t_{i+2}-t_{i+1})} , \qquad x \in (t_{i+1},t_{i+2}]\\
        0, \qquad otherwise
    \end{array}       
    \right.
\end{displaymath}
Finding the limit of knots $t_i-$ and $t_{i+1}$
\begin{equation}
    \lim_{x\rightarrow t_i^-}\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(x)=\frac{2}{t_{i+1}-t_i}=\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(t_i) \notag
\end{equation}
\begin{equation}
    \lim_{x\rightarrow t_{i+1}^-}\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(x)=\frac{-2}{t_{i+2}-t_i}=\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(t_{i+1}) \notag
\end{equation}
Thus, $\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(x)$ is continuous at $t_i$ and $t_{i+1}$.

\subsection{(c)}
Solution:\\
From (b), we know 
$\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(x) > 0, x \in (t_{i-1}, t_i]$ and $\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(x)$ monotonically decreasing in the interval $(t_i, t_{i+1}]$.\\
    Since $\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(x)$ is continuous at $t_i$,\\
    $\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(x)$ monotonically decreasing in the interval $[t_i, t_{i+1}]$.\\
    Since $\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(t_i) > 0$ and $\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(t_{i+1}) < 0$,\\
    only one $x^* = \frac{t_{i+2}t_{i+1}-t_i t_{i-1}}{t_{i+2}+t_{i+1}-t_i-t_{i-1}} \in (t_{i-1}, t_{i+1})$ satisfies $\frac{\mathrm{d}}{\mathrm{d}x}B_i^2(x^*) = 0$.

\subsection{(d)}
Solution:\\    
From (c) we know that 
\begin{displaymath}
    \frac{\mathrm{d}}{\mathrm{d}x}B_i^2(x)\left\{
        \begin{array}{l}
        > 0 , \qquad x \in (t_{i-1},x^*)\\
        = 0 , \qquad x = x^*\\
        < 0 , \qquad x \in (x^*,t_{i+2}]\\
        0, \qquad otherwise
    \end{array}       
    \right.
\end{displaymath}
Thus
$$max(B_i^2(x)) = B_i^2(x^*) = \frac{t_{i+2}-t_{i-1}}{t_{i+2}-t_{i-1}+t_{i+1}-t_{i}} < 1$$
$$min(B_i^2(x)) = min{B_i^2(t_{i-1}), B_i^2(t_{i+2})} = 0$$
Therefore $B_i^2(x) \in [0, 1)$.

\subsection{(e)}
Solution:\\
If $t_i = i$
\begin{displaymath}
    B_i^2(x)=\left\{
        \begin{array}{l}
        \frac{{(x-(i-1))}^2}{2}, \qquad \qquad  x \in (i-1,i]\\
        \frac{(x-(i-1))(i+1-x)}{2}+\frac{(i+2-x)(x-i)}{2}, \quad x \in (i,i+1]\\
        \frac{{(i+2-x)}^2}{2},\qquad x \in (i+1,i+2]\\
        0,  \qquad otherwise
        \end{array} 
    \right.
\end{displaymath}
\begin{figure}[H]
    \centering
    \includegraphics[scale=0.8]{./5_e.png}
\end{figure}

\section{$\uppercase\expandafter{\romannumeral6}$}
Solution:\\
From $B_i^{n+1}(x) = \frac{x - t_{i-1}}{t_{i+n} - t_{i-1}}*B_i^n(x) + \frac{t_{i+n+1} - x}{t_{i+n+1} - t_i}*B_{i+1}^n(x)$ and $B_i^0(x)=(t_i-t_{i-1})[t_{i-1},t_i](t-x)_+^0$, we can get
\begin{align}
  B_i^1(x) &= \frac{x-t_{i-1}}{t_i-t_{i-1}}B_i^0(x)+\frac{t_{i+1}-x}{t_{i+1}-t_i}B_{i+1}^0(x) \notag \\
  &= (x-t_{i-1})[t_{i-1},t_i](t-x)^0_+ + (t_{i+1}-x)[t_i,t_{i+1}](t-x)^0_+ \notag
\end{align}
Since $[t_{i-1},\ldots,t_{i+n}](t-x)^{n+1}_+ = (t_{i-1}-x)[t_{i-1},\ldots,t_{i+n}](t-x)^n_+$,
$$B^1_i(x) = (t_{i+1}-t_{i-1})[t_{i-1},t_i,t_{i+1}](t-x)^1_+.$$
Similarly, we can get
\begin{align}
  B_i^2(x)& = \frac{x-t_{i-1}}{t_{i+1}-t_{i-1}}B^1_i(x) + \frac{t_{i+2}-x}{t_{i+2}-t_i}B^1_{i+1}(x) \notag\\
  & = (x-t_{i-1})[t_{i-1},t_i,t_{i+1}](t-x)^1_+ + (t_{i+2}-x)[t_i,t_{i+1},t_{i+2}](t-x)^1_+ \notag \\
  & = [t_i,t_{i+1},t_{i+2}](t-x)^2_+ - [t_{i-1},t_i,t_{i+1}](t-x)^2_+ \notag \\
  & = (t_{i+2}-t_{i-1})[t_{i-1},t_i,t_{i+1},t_{i+2}](t-x)^2_+ \notag
\end{align}

\section{$\uppercase\expandafter{\romannumeral7}$}
Solution:\\
Because $\frac{\mathrm{d}}{\mathrm{d}x}B_i^n(x)$ is symmetric on $[t_i, t_{i+n}]$,
$$0 = \int_{t_{i-1}}^{t_{i+n}}\frac{d}{dx}B^n_i(x).$$
Since
$$\frac{\mathrm{d}}{\mathrm{d}x}B_i^n(x)=\frac{nB_i^{n-1}(x)}{t_{i+n-1}-t_{i-1}}-\frac{nB^{n-1}_{i+1}(x)}{t_{i+n}-t_i},$$
we can get
$$0=\frac{n}{t_{i+n-1}-t_{i-1}}\int_{t_{i-1}}^{t_{i+n}}B_i^{n-1}(x)dx-\frac{n}{t_{i+n}-t_i}\int_{t_{i-1}}^{t_{i+n}}B^{n-1}_{i+1}(x)dx.$$
Thus 
$$\frac{1}{t_{i+n-1}-t_{i-1}}\int_{t_{i-1}}^{t_{i+n}}B_i^{n-1}(x)dx=\frac{1}{t_{i+n}-t_i}\int_{t_{i-1}}^{t_{i+n}}B_{i+1}^{n-1}(x)dx = C.$$
Because $B^{n-1}_i(x)|_{t_{i+n-1}, t_{i+n}} = 0$, $[t_{i-1},t_i],B^{n-1}_{i+1}|_{t_{i-1}, t_i} = 0$,so
$$\frac{1}{t_{i+n}-t_i}\int_{t_{i}}^{t_{i+n}}B_{i+1}^{n-1}(x)dx = C, \forall i \in \mathbb{Z}.$$

\section{$\uppercase\expandafter{\romannumeral8}$}
\subsection{(a)}
Solution:\\
Let $m=4,n=2$, the table of divided difference is\\
\scalebox{0.8}{
\begin{tabular}{c|ccc}
$x_i$ & $x_i^4$\\ 
$x_{i+1}$ & $x_{i+1}^4$ & $x_{i+1}^3+x_{i}x_{i+1}^2+x_{i}^2x_{i+1}+x_{i}^3$\\
$x_{i+2}$ & $x_{i+2}^4$ & $x_{i+2}^3+x_{i+1}x_{i+2}^2+x_{i+1}^2x_{i+2}+x_{i+1}^3$ & $x_{i+2}^2+x_{i+1}^2+x_{i}^2+x_{i}x_{i+1}+x_{i}x_{i+2}+x_{i+1}x_{i+2}$
\end{tabular}
}\\
Therefore we can get\\
$$[x_i,x_{i+1},x_{i+2}]x^4=\tau_{2}(x_i,x_{i+1},x_{i+2}).$$
\subsection{(b)}
Solution:\\
\begin{align}
    &(x_{n+1}-x_1)\tau_k(x_1,\dots,x_n,x_{n+1}) \notag\\
    & = \tau_{k+1}(x_1,\dots,x_n,x_{n+1}) - \tau_{k+1}(x_1,\dots,x_n) - x_1\tau_k(x_1,\dots,x_n,x_{n+1}) \notag\\
    & = \tau_{k+1}(x_2,\dots,x_n,x_{n+1}) + x_1\tau_k(x_1,\dots,x_n,x_{n+1})  - \tau_{k+1}(x_1,\dots,x_n) - x_1\tau_k(x_1,\dots,x_n,x_{n+1}) \notag\\
    & = \tau_{k+1}(x_2,\dots,x_n,x_{n+1}) - \tau_{k+1}(x_1,\dots,x_n). \notag
\end{align}
Then we use mathematical induction:\\
For $k = 0$,
$$\tau_m(x_i) = [x_i]x^m,$$
obviously established.\\
For $k = n+1$,
\begin{align}
  &\tau_{m-n-1}(x_i,...,x_{i+n+1}) \notag\\
  & = \dfrac{\tau_{m-n}(x_{i+1},...,x_{i+n+1})-\tau_{m-n}(x_i,...,x_{i+n})}{x_{i+n+1}-x_{i}} \notag\\
  & = \dfrac{[x_{i+1},...,x_{i+n+1}]x^m-[x_{i},...,x_{i+n}]x^m}{x_{i+n+1}-x_{i}} \notag\\
  & = [x_{i},...,x_{i+n+1}]x^m. \notag
\end{align}
We completed the certification.
\end{document}
